package com.ocean.sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] nums = {8, 3, 9, 7, 1, 2, 5};
        mergeSort.mergeSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }

    private void mergeSort(int[] nums, int n) {
        mergeSort(nums, 0, n - 1);
    }

    private void mergeSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }


    private void merge(int[] nums, int start, int mid, int end) {
        int[] temp = new int[(end - start) + 1];
        int i = start;
        int j = mid + 1;
        for (int k = 0; k < temp.length; k++) {
            if (i > mid) {
                temp[k] = nums[j++];
            } else if (j > end) {
                temp[k] = nums[i++];
            } else if (nums[i] < nums[j]) {
                temp[k] = nums[i++];
            } else {
                temp[k] = nums[j++];
            }
        }
        // 将临时数组拷贝回原来得数组
        for (int n = 0; n < temp.length; n++) {
            nums[start + n] = temp[n];
        }

    }


//    private int[] mergeSort(int[] nums) {
//        if (nums.length < 2) {
//            return nums;
//        }
//        int mid = nums.length / 2;
//        int[] left = Arrays.copyOfRange(nums, 0, mid);
//        int[] right = Arrays.copyOfRange(nums, mid, nums.length);
//        return merge(mergeSort(left), mergeSort(right));
//    }
//
//    private int[] merge(int[] left, int[] right) {
//        int[] result = new int[left.length + right.length];
//        int n = result.length;
//        int i = 0;
//        int j = 0;
//        for (int k = 0; k < n; k++) {
//            if (i >= left.length) {
//                result[k] = right[j++];
//            } else if (j >= right.length) {
//                result[k] = left[i++];
//            } else if (left[i] > right[j]) {
//                result[k] = right[j++];
//            } else {
//                result[k] = left[i++];
//            }
//        }
//        return result;
//    }

}
